#include <iostream>
#include <vector>

using namespace std;

// TODO: optimize dp(i,j) = square right and bottom conner = [i,j], its largest legth

class Solution
{
public:
    int maximalSquare(vector<vector<char>> &matrix)
    {
        int minSize = min(matrix.size(), matrix[0].size());
        if (minSize == 0)
            return minSize * minSize;
        int size = 0;
        for (int i = 0; i < matrix.size(); i++)
        {
            for (int j = 0; j < matrix[0].size(); j++)
            {
                if (matrix[i][j] == '1')
                    size = 1;
            }
        }
        if (size == 0)
            return 0;
        for (int i = 2; i <= minSize; i++)
        {
            for (int x = 0; x < matrix.size() - i + 1; x++)
            {
                for (int y = 0; y < matrix[0].size() - i + 1; y++)
                {
                    matrix[x][y] = matrix[x][y] == '1' && matrix[x][y + 1] == '1' && matrix[x + 1][y] == '1' && matrix[x + 1][y + 1] == '1' ? '1' : '0';
                    if (matrix[x][y] == '1')
                        size = i;
                }
            }
            if (size != i)
                break;
        }
        return size * size;
    }
};

int main()
{
    cout << "Code221" << endl;
    Solution s;
    vector<vector<char>> matrix = {{'1', '1', '1', '1', '0'},
                                   {'1', '1', '1', '1', '0'},
                                   {'1', '1', '1', '1', '1'},
                                   {'1', '1', '1', '1', '1'},
                                   {'0', '0', '1', '1', '1'}};
    cout << s.maximalSquare(matrix) << endl;
    return 0;
}